package main

import (
	"fmt"
)

/*
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

作者：宫水三叶
链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r85adr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func minFallingPathSum(matrix [][]int) int {
	var dp [][]int
	for i := 0; i < len(matrix); i++ {
		dp = append(dp, make([]int, len(matrix[i])))
	}
	// base case
	for i := 0; i < len(matrix[0]); i++ {
		dp[0][i] = matrix[0][i]
	}
	minPath := 999
	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			if i == 0 {
				if i == len(dp)-1 {
					if minPath > dp[i][j] {
						minPath = dp[i][j]
					}
				}
				continue
			}
			if j == 0 {
				if j+1 < len(dp[i]) {
					dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
				} else {
					dp[i][j] = dp[i-1][j] + matrix[i][j]
				}
			} else if j == len(dp[i])-1 {
				if j-1 >= 0 {
					dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + matrix[i][j]
				} else {
					dp[i][j] = dp[i-1][j] + matrix[i][j]
				}
			} else {
				dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + matrix[i][j]
			}
			if i == len(dp)-1 {
				if minPath > dp[i][j] {
					minPath = dp[i][j]
				}
			}
		}
	}
	// for i := 0; i < len(dp); i++ {
	// 	fmt.Println(dp[i])
	// }
	return minPath
}

/*
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

请你返回非零偏移下降路径数字和的最小值。

作者：宫水三叶
链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r8oh2h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func minFallingPathSumWithOffset(arr [][]int) int {
	var dp [][]int
	var res [][][]int
	for i := 0; i < len(arr); i++ {
		dp = append(dp, make([]int, len(arr[i])))
		res = append(res, make([][]int, len(arr[i])))
	}
	// base case
	var last2MinCol [2]int = [2]int{0, 1} // 记录最小值和次小值位置，因为如果最小值位置在当前位置的正上方，就需要使用次小值
	for i := 0; i < len(dp[0]); i++ {
		dp[0][i] = arr[0][i]
		res[0][i] = append(res[0][i], arr[0][i])
		if i >= 1 {
			if dp[0][i] < dp[0][last2MinCol[0]] {
				last2MinCol[1] = last2MinCol[0]
				last2MinCol[0] = i
			} else if dp[0][i] < dp[0][last2MinCol[1]] {
				last2MinCol[1] = i
			}
		}
	}
	// 状态转移
	for i := 1; i < len(dp); i++ {
		fmt.Println("last2MinCol", last2MinCol)
		var tmpLevelLast2Min [2]int = [2]int{0, 1}
		for j := 0; j < len(dp[i]); j++ {
			if j != last2MinCol[0] {
				dp[i][j] = dp[i-1][last2MinCol[0]] + arr[i][j]
			} else {
				dp[i][j] = dp[i-1][last2MinCol[1]] + arr[i][j]
			}
			// 更新当前层的最小与次小值
			if j >= 1 {
				if dp[i][j] <= dp[i][tmpLevelLast2Min[0]] {
					tmpLevelLast2Min[1] = tmpLevelLast2Min[0]
					tmpLevelLast2Min[0] = j
				} else if dp[i][j] < dp[i][tmpLevelLast2Min[1]] {
					tmpLevelLast2Min[1] = j
				}
			}
		}
		last2MinCol = tmpLevelLast2Min
	}
	for i := 0; i < len(dp); i++ {
		fmt.Println(dp[i])
	}
	return dp[len(dp)-1][last2MinCol[0]]
}

func min(args ...int) int {
	m := args[0]
	for _, d := range args {
		if d < m {
			m = d
		}
	}
	return m
}

func main() {
	matrix := [][]int{
		{-73, 61, 43, -48, -36},
		{3, 30, 27, 57, 10},
		{96, -76, 84, 59, -15},
		{5, -49, 76, 31, -7},
		{97, 91, 61, -46, 67},
	}
	// matrix = [][]int{
	// 	{-19},
	// }
	fmt.Println(minFallingPathSumWithOffset(matrix))
}
